package test230602;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/2 22:41
 * 338. 比特位计数
 * https://leetcode.cn/problems/counting-bits/
 */
public class Solution04 {

    public int[] countBits(int n) {
        // count[i] 表示数字 i 的二进制表示中 1 的个数
        int[] count = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            if ((i & 1) == 1) {
                // 如果 i 是一个奇数, 则二进制位置会损失 1 个 1
                count[i] = count[i >> 1] + 1;
            } else {
                // 如果是偶数, 其二进制表示的 1 的个数没有损失
                count[i] = count[i >> 1];
            }
        }
        return count;
    }
}
